今天的主題是 Loop，也就是迴圈。迴圈是一種常見的控制流程，意思是一段程式，我們可以執行特定次數，或者是當某個條件成立時，就停止執行。當然我們有時候會不小心寫出 Bug，造成條件永遠不成立，那麼就會變成所謂的無限迴圈啦！一般來說迴圈大概會有 For-loop (指定執行次數), while/do-while (指定條件的迴圈)。

Hackerrank 在 Loop 這個主題的題目是類似把九九乘法表印出來，但是為了展示更多東西，我們今天來寫個計算階乘吧！例如當我給的數字是 5，那麼我的結果就應該是要 1 x 2 x 3 x 4 x 5。不過我們當然不會這麼簡單，而是要深入來看看為什麼各語言可以這麼做。另外在 Scala 我們通常會用 Functional programming 的風格來撰寫，所以我們最後再來講 Scala，因為我們會直接用遞迴取代 Loop 來避免我們去使用到 mutable 的變數囉！(Loop 比較是 Imperative programming 的用法) (當然其他語言也可以用遞迴，但是在 Scala 幾乎是看不到 Loop 的唷，甚至有為遞迴去做優化呢！所以 Scala 的部分將直接用遞迴去闡述)

Python 3

def factorial(n):
  fact = 1
  for i in range(1, n + 1): 
    fact = fact * i 
  return fact 
  
print (factorial(5))   
print (factorial(10)) 

• Python 的 For loop 比較不像我們平常在例如 C 語言所看到的 for(INITIALIZATION, CONDITION, AFTERTHOUGHT) 像是 for(int i = 0; i < 100; i++) 。在 Python 這裡for i in range(1, n + 1) 表示現在要 Iterate in 後面的 range(1, n + 1) ，並且每次都把 Interate 的結果存到 i 裡頭，讓 for 的程式區塊可以去利用。range 是 Python 內建函數，會回傳整數序列，而整數序列是個可迭代 Object (例如 range(0, 5)會得到 0, 1, 2, 3, 4的整數序列。 in 後面可以放的還有像是 list, string 等等可迭代的 Object。
• 什麼是可迭代 Object 呢？可迭代 Object 必須要有__iter__() and __getitem__() 兩個方法。我們可以用 hasattr(<object>, '__iter__') 和 hasattr(<object>, '__getitem__') 來得知。例如 hasattr(range(5), '__iter__') , hasattr([1, 2, 3], '__iter__') , hasattr('abc', '__iter__') 都是 True。現在讓我們來講另一個聽起來很像的東西叫做 Iterator (迭代器)，要成為一個迭代器，必須要實作__iter()__ (返回自己)和 next() (返回下一個元素)。 next() 從字面上的意義我們大概就可以想見這是一個在迭代過程中用來讓我們得到“容器” (就是像上面的 List, String 等等) 中的下一個元素用的。那麼剛才我們說的那些可迭代對象是不是迭代器呢？以 [1 ,2, 3] 為例，我們看到 hasattr([1, 2, 3], 'next') 居然是 False！所以像是 List、Range、String 等等本身還不是迭代器。回到我們的 For loop，其實在 Python 的 for 語句會先把可迭代 Object 透過內建的 iter() 函數，將其變成一個迭代器，所以我們才可以透過 next() 來得到下一個元素囉！那我們能不能把自己的 Class 變成迭代器？當然可以，只要實作__iter()__ (返回自己)和 next() (返回下一個元素)。有興趣可以參考這裡囉
• 除了 for，當然還是像是 while 這種根據條件決定是否繼續執行的迴圈結構。而這種迴圈又會有 break , continue 來脫離迴圈或是提早結束此次執行的語句，在這就不贅述了。

Golang

package main

import "fmt"

func factorial(n int) int {
  fact := 1
  for i := 1; i <= n; i++ {
    fact = fact * i
  }
  return fact
}

func main() { 
   fmt.Println(factorial(5))
   fmt.Println(factorial(10))
}

• 基本上應該不難理解上面的程式，我們這裡 for 的寫法是 for(INITIALIZATION, CONDITION, AFTERTHOUGHT) 的結構。比較特別的是，在 Golang 並沒有像是 while 的語句。我們曾說到 Golang 為了簡潔，關鍵字很少，所以迴圈結構只有 for 這個關鍵字。假如我們要有 while 的效果，會寫成 for <Condition> { ... } 這裡的 Condition 就是 while條件的條件。如果寫成 for { ... } 那就是個無窮迴圈囉！而 Golang 一樣也有 break 跟 continue 。像 break 通常就會搭配 for { ... } 來使用囉。
• 接著我們來看 range ，在 Golang 裡頭 range 並不像是 Python 產生一個可迭代 Object、一個數字序列 (like range(5))，而是一個關鍵字，讓你可以 iterate 像是 slice , map 。先大概講講 slice 和 map 是什麼。我們可以把 slice 看成是可變大小的 Array (當然你可以指定大小上限)，是可索引的，例如 a := []int{1, 2, 3} 就是一個元素是 int的 slice。而 map 是存放 key-value pairs，像是 python 的 Dictionary，例如 map[string]string{"a": "apple", "b": "banana"} 就是一個 Key 和 value 都是 string 的 map 。我們要講的 range 就是可以 iterate 像是slice , map 的資料結構。例如下面分別 range slice 跟 map， range slice 時回傳 index 跟數字 (index 從 0 開始)，而 ``range map` 時會回傳 key 跟 value。

sum := 0
for index, num := range []int{1, 2, 3} {
  fmt.Println("index:", index)
  sum += num
}
m := map[string]string{"a": "apple", "b": "banana"}
for key, value := range m {
  fmt.Printf("%s -> %s\n", key, value)
}

• 那麼我們能不能像 Python 一樣，在 Golang 將自定義的 Struct 去實作一些方法來給 range 做 iteration 呢？目前就我看下來是沒有辦法的，或是說可能也沒有必要。因為很多時候我們要做 iterate 時，其實都是可以將元素拷貝到 slice 裡頭去做 iterate，加上 Golang 在 iterate slice 和 map 時，其實都有做效能上的優化唷！

Rust

fn factorial(n: i32) -> i32 {
  let mut fact: i32 = 1;
  for num in 1..n+1 {
    fact = fact * num;
  }
  fact
} 

fn main() {
  println!("{}", factorial(5));
  println!("{}", factorial(10));
}

• 在 Rust 的部分，要做到這件事情可以有很多方式，雖然 Rust 有提供很多 Functional programming 風格的 API，但 Rust 還是以 Imperative programming 為主，所以我們還是介紹使用 Rust 的 for 來解囉。
• 這裡的 Code 應該也很好理解，首先再次提醒 fact 要定義成 mut 不然是無法被修改的。 for num in 1..n+1 表示這裡會 interate 1, 2, 3, … n 並且綁定到 num 去做使用。在 Rust 的 for是 for <var> in <expression> 的形式，不同於 C-Style 的 for(INITIALIZATION, CONDITION, AFTERTHOUGHT) ，跟 Python 一樣。Okay，邏輯講完了，我們來看 Rust 的 Iterator。
• 首先我們先來看看有沒有辦法直接 Iterate 一個 Array 呢？例如 for num in [1, 2, 3] { ... } ，結果你會看到 Compiler 跟你說 call .iter() onit to iterate over it ，也就是我們必須寫成 for num in [1, 2, 3].iter() { ... } ，來把 [1, 2, 3] 變成一個 Iterator，也就是說 for 要能夠作用， in 後面的必須是個 Iterator。那麼要如何實作一個 Iterator 呢？就是必須要實作 trait Iterator，內容可參考這裡 。我們可以從文件看到，必須 (Required Methods)要實作的是 next這個 Function ( fn next(&mut self) -> Option<Self::Item> )， next從字面意義我們可以想見是取出下一個值，而其 Return 的是一個 Option ， Option是個 Enum Type (之前提過 Result也是 )，他的 variants 有 Some跟 None 。我們在這裡可以把Option想成是一個容器 ，如果有下一個值的話，就會把值放在 Some裡頭並回傳 Some(下一個值) ，如果已經沒有了就會回傳 None 。至於 Item 是這個 Trait 所定義的 Associated type，有興趣的可以參考這裡。簡單來說就是當你要 Impl 這個 Trait 的時候，你必須也要指定一個真正的 Type 給 Item ，於是在 Trait 裡頭的方法如果定義用到了 Self::Item 的部分，就會替換成你指定給 Item的 Type。這裡有個實作一個 Fibonacci 數列的 Iterator 可參考 。最後來講下 for num in [1, 2, 3].iter() { ... } 的 num 在程式區塊中是 immutable 的，如果你要讓它是 mutable 的話，就要用 iter_mut() 唷！
• Rust 還有一個真的叫做 loop 的語法，概念上就是可以不斷重複 loop 的程式區塊，直到你顯性地用 break 來離開這個 loop 。更特別的是， loop 也是可以 Return 值的唷 (放在 break之後)！例如下面的 result 最後會是 5 。

let mut counter = 0;
let result = loop {         
  counter += 1;          
  if counter == 5 {             
    break counter;         
  }    
};

• 這邊再來看另一個方式來解決這個問題。 這裡的 fold 的第一個參數是 initial value ( 1)，而第二個參數是個 closure，可以想成是其他語言的 lambda function。 fold就像是其他語言的 reduce 的效果，會 iterate 1..n+1 的元素，並且放到 closure 的 n ，持續地跟 acc 相乘，最後全部 iterate 完後，會回傳 acc 的值。這裡 acc初始值就是 fold 的第一個參數 1 ，所以第一次的 iteration 會是 11 (此時 acc 變為 1)，再來是 12 (此時 acc 變為 2)，再來是 2*3 (此時 acc 變為 6)，持續下去直到 iterate 結束便可以得到 n 的階層了。而這樣的方式就是 Functional 的寫法囉！

fn factorial(n: i64) -> i64 {
    (1..n+1).fold(1, |acc, n| acc * n)
}

Scala

object Factorial {
    
    def factorial(n: Int): Int = n match {
        case 0 => 1
        case _ => n * factorial(n-1)
    }    

    def factorialTail(n: Int): Int = {
        def factorialTailHelper(n: Int, acc: Int): Int = n match {
            case 0 => acc
            case _ => factorialTailHelper(n-1, acc * n)
        }
        factorialTailHelper(5, 1)
        
    }        
    
   def main(args: Array[String]) {
      println(factorial(5))
      println(factorialTail(5))
   }
   
}

• 首先看到 def factorial(n: Int): Int 這個 Function，我們用遞迴的方式就可以避免去使用 mutable 的變數來不斷地來更新結果。而遞迴會需要一個終止條件，在這裡就是當 n match 0 的時候就回傳 1 ，所以我們來看看例如 n 等於 5 時候會發生什麼事： 5 * factorial(4) => 5 * 4 * factorial(3) =>5 * 4 * 3 * factorial(2) => 5 * 4 * 3 * 2 * factorial(1) => 5 * 4 * 3 * 2 * 1 * factorial(0) => 5 * 4 * 3 * 2 * 1 * 1 這樣就完成整個遞迴的過程啦，過程之中也不會再有一個變數來存狀態 (目前的乘積)，就像是算數學一樣一路算出答案。那麼這樣會有什麼問題呢？當程式遇到 recursion 時，必須保存當時的執行狀態，以利之後返回並計算，而這些狀態就會被保存在 stack memory 中，如果遞迴過多，例如 factorial(1000000) ，就會造成 stack memory 不夠，而有所謂的 stack overflow 的產生了。
• 要解決這個問題，我們必須讓我們的遞迴變成 tail recursion，也就是最後必須是直接 call 一個 Function (自己或別人)。我們來看 factorialTail 這個 Function 。首先我們可以看到 factorialTail 裡頭又有一個 Function 叫 factorialTailHelper (Scala 讓你可以在函式裡面定義函式)，而 factorialTailHelper 跟我們的 factorial Function 有點像，但是在遞迴的部分，並不是原先數字再乘上 call Function 的值，而是直接 call 一個 Function factorialTailHelper(n-1, acc*n) ，這就達到了所謂的 Tail recursion 的條件。那麼如何透過 Tail recursion 算出階乘呢？我們的做法是把結果給放在參數裡頭傳遞下去囉！所以我們來看看這會發生什麼事。首先看到這個 Function factorialTail 裏頭第一個執行的是 factorialTailHelper(5, 1) ，接著會是 factorialTailHelper(4, 5) =>factorialTailHelper(3, 20) =>factorialTailHelper(2, 60) => factorialTailHelper(1, 120) => factorialTailHelper(0, 120) => 120 。我們比較這兩種做法，第一種會 stack overflow 但直覺，而第二種比較不直覺、可讀性較差，但是比較安全，所以要用那一種，我想就看情境囉！嚴格來說，Scala 對於 Tail recursion 的效能優化，在 self-tail calls 才有效果，但是在 mutual recursion 就無法了 (兩個 Function 互 call)，所以要注意。Compiler 在 self-tail calls 這種 Tail recursion，其實會轉換成 for-loop，所以每一次 Tail call 都會把之前 Stack 內的上一層給清掉，所以就算再多的 recursion 也不會 Overflow 了。

結語

今天這一篇花了很多的時間，主要介紹了 Iterator 和在 Scala 使用遞迴的一些觀念，希望能給大家帶來幫助囉！明天見囉！

(今日字數：8229 字)